// 给定两个非空链表的头节点l1和l2来代表两个非负整数，数字最高位位于链表开始位置，每个节点只存储一位数字，除了数字0外，这个两个链表代表的数字都不会以0开头
// 要求将这两个数相加后返回一个新的链表

const { LinkedList, ListNode } = require("./64.设计链表")

// 思路：和上一题的不同之处在于链表从头到尾，代表数字位数从高到低，需要把链表的节点放到数组中操作
// 确定某个新节点时，连接低位的节点，最终返回新节点就是处于高位的头节点
// 时间复杂度：O(m+n)，m是链表l1的节点数，n是链表l2的节点数
// 空间复杂度：O(m+n)

function addTwoNumbers(head1, head2) {
    let stack1 = []
    let stack2 = []
    let cur1 = head1
    let cur2 = head2
    while (cur1) {
        stack1.push(cur1.val)
        cur1 = cur1.next
    }
    while (cur2) {
        stack2.push(cur2.val)
        cur2 = cur2.next
    }
    let sum = 0
    let curry = 0
    let res = null
    while (stack1.length || stack2.length || curry) {
        let nums1 = stack1.length ? stack1.pop() : 0
        let nums2 = stack2.length ? stack2.pop() : 0
        sum = nums1 + nums2 + curry
        curry = Math.floor(sum / 10)
        let newNode = new ListNode(sum % 10, res)
        res = newNode
    }
    return res
}

let l1 = new LinkedList([7,2,4,3]).head
let l2 = new LinkedList([5,6,4]).head
let result = addTwoNumbers(l1, l2)
console.log(result)